class Solution
{
public:
    string evaluate(string s, vector<vector<string>> &knowledge)
    {
        unordered_map<string, string> knowledgeDict;
        for (auto &knowledgePair : knowledge)
        {
            knowledgeDict[knowledgePair[0]] = knowledgePair[1];
        }

        string result;
        int n = s.size();
        int i = 0;
        while (i < n)
        {
            if (s[i] == '(')
            {
                int begin = i + 1;
                while (s[i] != ')')
                {
                    ++i;
                }
                string key = s.substr(begin, i - begin);
                if (knowledgeDict.count(key))
                {
                    result += knowledgeDict[key];
                }
                else
                {
                    result += '?';
                }
                ++i;
            }
            else
            {
                result += s[i];
                ++i;
            }
        }
        return result;
    }
};